# 方法一：暴力  复杂度O(N*M)
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 暴力 解法
        n=len(haystack)
        m=len(needle)
        for i in range(n):
            # 如果当前字符匹配，查看从i 到 i+m 这段区间的字符串是否等于 needle
            if haystack[i]==needle[0]:
                if haystack[i:i+m] == needle:
                    return i
        return -1

# 方法二：KMP算法,预先看KMP模板

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 方法二，KMP算法
        # 构建next数组
        def build_next(s):
            next = [0]
            i = 1
            length = 0  # 共同的长度
            while i < len(s):
                if s[length] == s[i]:
                    length += 1
                    next.append(length)
                    i += 1
                else:
                    # 查表不存在
                    if length == 0:
                        next.append(0)
                        i += 1
                    else:
                        length = next[length - 1]
            return next

        def KMP(s, c):
            next = build_next(c)
            print(next)
            i = 0
            j = 0
            while i < len(s):
                if s[i] == c[j]:  # 当前字符匹配
                    i += 1
                    j += 1
                elif j > 0:  # 字符不匹配，根据next数组跳过前面的一些字符
                    j = next[j - 1]
                else:
                    i += 1
                if j == len(c):
                    return i - j
            return -1

        return KMP(haystack, needle)
